#include <stdio.h>
#include <stdlib.h>
#include "graph.h"

int Init(Graph *graph)
{
	graph->MaxVertex = Default_Vertex_Size;
	graph->NumVertex = graph->NumEdge = 0;
	graph->NodeTable = malloc(sizeof(Vertex) * graph->MaxVertex);
	if (graph->NodeTable == NULL)
		return -1;
	for (int i = 0; i < graph->MaxVertex; i++)
		graph->NodeTable[i].adj = NULL;
	return 0;
}

int InsertVertex(Graph *graph, datatype data)
{
	if (graph->NumVertex == graph->MaxVertex)
		return -1;
	graph->NodeTable[graph->NumVertex++].data = data;
	return 0;
}

void Show(Graph *graph)
{
	for (int i = 0; i < graph->NumVertex; i++)
	{
		printf("%d %c:>", i, graph->NodeTable[i].data);
		Edge *p = graph->NodeTable[i].adj;
		while (p != NULL)
		{
			//printf("%d--> ", p->dest);
			printf("%c--> ", graph->NodeTable[p->dest].data);
			p = p->link;
		}
		printf("Nul.\n");
	}
}

int GetVertexPosion(Graph *graph, datatype vertex)
{
	for (int i = 0; i < graph->NumVertex; ++i)
	{
		if (graph->NodeTable[i].data == vertex)
			return i;
	}
	return -1;
}

int InsertEdge(Graph *graph, datatype vertex1, datatype vertex2)
{
	int p1 = GetVertexPosion(graph, vertex1);
	int p2 = GetVertexPosion(graph, vertex2);
	if (p1 == -1 || p2 == -1 || p1 == p2)
		return -1;
	// V1-->V2
	Edge *current = malloc(sizeof(Edge));
	if (current == NULL)
		return -2;
	current->dest = p2;
	current->link = graph->NodeTable[p1].adj;
	graph->NodeTable[p1].adj = current;
	// V2-->V1
	current = malloc(sizeof(Edge));
	if (current == NULL)
		return -3;
	current->dest = p1;
	current->link = graph->NodeTable[p2].adj;
	graph->NodeTable[p2].adj = current;
	++graph->NumEdge;
	return 0;
}

int RemoveEdge(Graph *graph, datatype vertex1, datatype vertex2)
{
	int p1 = GetVertexPosion(graph, vertex1);
	int p2 = GetVertexPosion(graph, vertex2);
	if (p1 == -1 || p2 == -1)
		return -1;
	Edge *p = NULL, *q = NULL;  //q是p的前驱

	//删除V1-->V2边
	p = graph->NodeTable[p1].adj;
	while (p != NULL && p->dest != p2)
	{
		q = p;
		p = p->link;
	}
	if (p != NULL)
	{
		if (q == NULL) // p指向的第一个结点就是要找的结点,这时候q还为空
			graph->NodeTable[p1].adj = p->link;
		else
			q->link = p->link;
		free(p);
	}
	else     //根本就没有边存在
		return -2;

	//删除V2-->V1边
	p = graph->NodeTable[p2].adj;
	q = NULL;
	// V1-->V2有边，那么V2-->V1就一定有边,否则这个图的结构就是错误的,所以这里不需要p==NULL的判断
	while (p->dest != p1)
	{
		q = p;
		p = p->link;
	}
	if (q == NULL) // p指向的第一个结点就是要找的结点,这时候q还为空
		graph->NodeTable[p2].adj = p->link;
	else
		q->link = p->link;
	free(p);

	--graph->NumEdge;

	return 0;
}

int RemoveVertex(Graph *graph, datatype vertex)
{
	int p1 = GetVertexPosion(graph, vertex);
	if (p1 == -1)
		return -1;

	//删除与结点关联的边
	#if 1
	Edge *pre = NULL, *current, *next;
	current = graph->NodeTable[p1].adj;
	while (current != NULL)
	{
		int p2 = current->dest;
		next = graph->NodeTable[p2].adj;
		while (next->dest != p1)
		{
			pre = next;
			next = next->link;
		}
		if (pre == NULL)
			graph->NodeTable[p2].adj = next->link;
		else
			pre->link = next->link;
		free(next);
		graph->NodeTable[p1].adj = current->link;
		free(current);
		current = graph->NodeTable[p1].adj;
		--graph->NumEdge;
	}
	#endif 

	//直接调用RemoveEdge()的写法
	#if 0
	Edge *current = graph->NodeTable[p1].adj;
	Edge *next;
	while (current != NULL)
	{
		datatype p2 = graph->NodeTable[current->dest].data;
		RemoveEdge(graph, p1, p2);
		current = current->link;
	}
	#endif

	//删除结点
	--graph->NumVertex;
	graph->NodeTable[p1].data = graph->NodeTable[graph->NumVertex].data;
	graph->NodeTable[p1].adj = graph->NodeTable[graph->NumVertex].adj;
	current = graph->NodeTable[p1].adj;
	while (current != NULL)
	{
		int k = current->dest;
		next = graph->NodeTable[k].adj;
		while (next != NULL)
		{
			if (next->dest == graph->NumVertex)
			{
				next->dest = p1;
				break;
			}
			next = next->link;
		}
		current = current->link;
	}
	return 0;
}

void Destory(Graph *graph)
{
	Edge *p;

	for (int i = 0; i < graph->NumVertex; i++)
	{
		while ((p = graph->NodeTable[i].adj) != NULL)
		{
			graph->NodeTable[i].adj = p->link;
			free(p);
		}
	}
	free(graph->NodeTable);
	graph->NodeTable = NULL;
	graph->NumVertex = graph->NumEdge = 0;
}

int GetFirstNeighbor(Graph *graph, datatype vertex)
{
	int p = GetVertexPosion(graph, vertex);
	if (p == -1)
		return -1;
	Edge *current = graph->NodeTable[p].adj;
	if (current != NULL)
		return current->dest;
	return -2;
}

int GetNextNeighbor(Graph *graph, datatype vertex1, datatype vertex2)
{
	int p1 = GetVertexPosion(graph, vertex1);
	int p2 = GetVertexPosion(graph, vertex2);
	if (p1 == -1 || p2 == -1 || p1 == p2)
		return -1;
	Edge *current = graph->NodeTable[p1].adj;
	while (current != NULL && current->dest != p2)
		current = current->link;
	if (current == NULL) // vertex2不是vertex1的邻接顶点
		return -2;
	else if (current->link != NULL)
		return current->link->dest;
	return -3;
}